package zisu.algorithm.algorithm.AStart;

import java.util.ArrayList;
import java.util.Scanner;
import java.util.Stack;

public class AStart {
    /*
     * (sx,sy) is the coordinate of the start Node,(ex,ey) is the coordinate of the end(goal) Node
     * in the Searched Map, 1 is the path & 0 is the barrier，for example：
     * 1 1 1 1 1
     * 1 0 0 1 0
     * 1 1 1 1 0
     * 1 1 1 1 1
     */


    //todo 这里map 应该是本地读取出来的（静态）。充电桩用什么表示再说。
    Node [][] map;
    int sx, sy, ex, ey;
    int lengthx, lengthy;
    ArrayList<Node> openList;
    //ArrayList<Node> closeList;
    public AStart(int sx, int sy, int ex, int ey) {
        this.sx = sx;
        this.sy = sy;
        this.ex = ex;
        this.ey = ey;
        openList = new ArrayList<Node>();
        //closeList = new ArrayList<Node>();
    }
    //todo 初始化地图应该不是在这里初始化的。
    public void init(int lengthx, int lengthy) {
        map = new Node[lengthx + 1][lengthy + 1];
        this.lengthx = lengthx;
        this.lengthy = lengthy;
    }

    public void setNode(int x, int y, int val) {
        map[x][y] = new Node(x,y,val);
    }
    private int calH(int x, int y) {
        return 10*(Math.abs(x-ex)+Math.abs(y-ey));
    }
    public void AstarSearch() {
        //1.把起点加入openList
        if(map[sx][sy].val!=1){
            System.out.println("The start Node value must be 1");
            return;
        }
        openList.add(map[sx][sy]);
        map[sx][sy].H = this.calH(sx, sy);
        map[sx][sy].G = 0;
        map[sx][sy].F = map[sx][sy].H + map[sx][sy].G;
        int Fmin = 2147483647;

        //2.重复以下步骤：
        // a.遍历open list查找F最小的节点，视作当前要处理的点
        while(!openList.isEmpty()) {
            int currentNodeIndex = 0; //这里由于openList.remove需要已知的参数，因此要初始化
            // 找出F 最小的节点。
            for(int i=0; i<openList.size(); i++) {
                if(openList.get(i).F < Fmin) {
                    currentNodeIndex = i;
                    Fmin = openList.get(i).F;
                }
            }
            Node currentNode = openList.get(currentNodeIndex);

            Node nextNode;
            //b.把这个点移到closeList(7.31此时有疑问？移到closeList中去要把它从openList中删除吗？假设删除！
            currentNode.closed = true;
            openList.remove(currentNodeIndex);
            //c.对当前方格的相邻8个方格中的每一个：
            //todo here
            for(int i=-1; i<=1; i++){
                for(int j=-1;j<=1;j++) {
                    //在找到一个新的节点的时候应该先判断这个是不是终点
                    // 如果是终点，那个把沿途的点压如栈中并且输出出来。
                    if(currentNode.x+i == ex && currentNode.y+j==ey) {
                        Node current = currentNode;//这两个点用于访问fatherNode输出路径
                        Stack<Node> sta = new Stack<Node>();
                        while(current.father!=null) {
                            sta.push(current);
                            current = current.father;
                        }
                        Node outputNode = null;
                        System.out.print("("+sx+","+sy+")->");
                        while(!sta.isEmpty()) {
                            outputNode = sta.pop();
                            System.out.print("("+outputNode.x+","+outputNode.y+")->");
                        }
                        System.out.print("("+ex+","+ey+")");
                        return;
                    }
                    // 判断currentNode 周围的区域是否合法。
                    if(currentNode.x+i>0 && currentNode.y+j>0 && currentNode.x+i <= lengthx && currentNode.y+j <=lengthy
                            && map[currentNode.x+i][currentNode.y+j].val ==1 && map[currentNode.x+i][currentNode.y+j].closed==false) {
                        //判断下一个点是否超出地图边界或者已经加入closeList或者是不可到达状态。
                        nextNode = map[currentNode.x + i][currentNode.y +j];
                        //todo here
                        if(!openList.contains(nextNode)) {
                            /*
                             *在第一种情况下，nextNode尚未被加入到openList，因此G还是初始化的无穷大
                             *可以直接将nextNode的父节点设置为currentNode
                             */
                            openList.add(nextNode);
                            nextNode.father = currentNode;
                            //对角线移动的情况（绝对值为2 说明是对角的方格）
                            if(Math.abs(i)+Math.abs(j)==2) {
                                nextNode.G = currentNode.G+14;
                                nextNode.H = calH(nextNode.x,nextNode.y);
                                //nextNode.H = 10*(Math.abs(nextNode.x - ex) + Math.abs(nextNode.y - ey));
                                nextNode.F = nextNode.G + nextNode.H;
                            }
                            else {
                                //水平（竖直）移动的情况
                                nextNode.G = currentNode.G + 10;
                                nextNode.H = 10*(Math.abs(nextNode.x - ex) + Math.abs(nextNode.y - ey));
                                //nextNode.H = 10*(Math.abs(nextNode.x - ex) + Math.abs(nextNode.y - ey));
                                nextNode.F = nextNode.G + nextNode.H;
                            }
                        }
                        else{
                            nextNode = map[currentNode.x + i][currentNode.y +j];
                            /*
                             * 在第二种情况下，nextNode已经存在于openList，需要判断是否有比之前
                             * 得到的更短的路径到达nextNode
                             */
                            if(Math.abs(i)+Math.abs(j)==2) {
                                //对角线移动的情况
                                if(currentNode.G + 14 < nextNode.G) {
                                    nextNode.G = currentNode.G+14;
                                    nextNode.H = 10*(Math.abs(nextNode.x - ex) + Math.abs(nextNode.y - ey));
                                    nextNode.F = nextNode.G + nextNode.H;
                                    nextNode.father = currentNode;
                                }
                            }
                            else {
                                //水平（竖直）移动的情况
                                if(currentNode.G + 10 < nextNode.G) {
                                    nextNode.G = currentNode.G+10;
                                    nextNode.H = 10*(Math.abs(nextNode.x - ex) + Math.abs(nextNode.y - ey));
                                    nextNode.F = nextNode.G + nextNode.H;
                                    nextNode.father = currentNode;
                                }
                            }
                        }
                    }
                }
            }

        }

        //如果存在openList为空的状态，即Astar搜索无法找到路径，跳出了while loop,警告无路径：
        System.out.println("Warning:There's no path between input Node!");
    }
    public static void main(String args[]) {
        Scanner scan = new Scanner(System.in);
        int lengthx = scan.nextInt();
        int lengthy = scan.nextInt();
        AStart as = new AStart(scan.nextInt(), scan.nextInt(), scan.nextInt(), scan.nextInt());
        as.init(lengthx, lengthy);
        for(int i=1; i<=lengthx; i++) {
            for(int j=1; j<=lengthy; j++){
                as.setNode(i,j,scan.nextInt());
            }
        }
        scan.close();
        as.AstarSearch();
    }
}

class Node{
    public int F,G,H;
    public int x,y; //coordinate in Map
    public boolean closed;	//算法中closeList中的元素不会被拿出来吧？？
    public int val;
    Node father;
    public Node(int x, int y, int val) {
        this.x = x;
        this.y = y;
        this.val = val;
        G = 2147483647;
        closed = false;
    }
}
